/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/11
 * \* Time: 17:22
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 零钱兑换1 {
    public int coinChange(int[] coins, int amount){
        //自底向上动态规划
        if(coins.length==0){
            return -1;
        }

        //memo[n]的值表示凑出面试为n的所需最少硬币个数
        int[] memo=new int[amount+1];
        memo[0]=0;
        for(int i=1;i<=amount;i++){
            int min=Integer.MAX_VALUE;
            for(int j=0;j<coins.length;j++){
                if(i-coins[j]>=0&&memo[i-coins[j]]<min){
                    min = memo[i-coins[j]] + 1;
                }
            }
            memo[i]=min;
        }
        return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
    }
}